package offer;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @Author Elephas
 * @Date 2022/1/20
 **/
public class PathSum {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum){
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> stack = new ArrayList<>();
        recPreOrderTraversal(ans,stack,root,targetSum);
        return ans;
    }
    public void recPreOrderTraversal(List<List<Integer>> ans,List<Integer> stack, TreeNode root,int targetSum){
        if(root == null){
            return;
        }
        stack.add(root.val);
        recPreOrderTraversal(ans,stack,root.left,targetSum);
        recPreOrderTraversal(ans,stack,root.right,targetSum);
        if( root.left == null && root.right == null){
            int sum = stack.stream().reduce(0,Integer::sum);
            if(sum == targetSum){
                List<Integer> temp = stack.stream().collect(Collectors.toList());
                ans.add(temp);
            }
        }
        stack.remove(stack.size()-1);
        return;
    }
}
